//给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 
//
// 
//
// 示例 1: 
//
// 输入: [2,3,-2,4]
//输出: 6
//解释: 子数组 [2,3] 有最大乘积 6。
// 
//
// 示例 2: 
//
// 输入: [-2,0,-1]
//输出: 0
//解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 
// Related Topics 数组 动态规划 
// 👍 741 👎 0

package leetcode.editor.cn;

//Java：乘积最大子数组
public class P152MaximumProductSubarray {

    /**
     *
     * 思路：动态规划，核心思路是要构建一个dp[i][j] 来表示以nums[i]为结尾的连续数字的乘积的最大值和最小值，然后考虑各种前一个数是大于0还是小于0还是等于0的情况
     *
     * 执行用时： 3 ms , 在所有 Java 提交中击败了 41.51% 的用户 内存消耗： 39.6 MB , 在所有 Java 提交中击败了 95.69% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxProduct(int[] nums) {
            if (nums.length == 0) {
                return 0;
            }

            // dp[i][j] 以nums[i]为结尾的连续数字的乘积值，j可以取0 1 ，代表最小最大值
            int dp[][] = new int[nums.length][2];
            dp[0][0] = nums[0];
            dp[0][1] = nums[0];

            for (int i = 1; i < nums.length; i++) {
                if (nums[i] < 0) {
                    // 上一个最小值大于0
                    if (dp[i - 1][0] > 0) {
                        dp[i][0] = dp[i - 1][1] * nums[i];
                        dp[i][1] = nums[i];
                    } else if (dp[i - 1][1] < 0) {
                        // 上一个最大值小于0
                        dp[i][1] = dp[i - 1][0] * nums[i];
                        dp[i][0] = nums[i];
                    } else {
                        if (dp[i - 1][1] == 0) {
                            dp[i][0] = nums[i];
                        } else {
                            dp[i][0] = dp[i - 1][1] * nums[i];
                        }
                        dp[i][1] = dp[i - 1][0] * nums[i];
                    }
                } else if (nums[i] > 0) {
                    // 上一个最小值大于0
                    if (dp[i - 1][0] > 0) {
                        dp[i][1] = dp[i - 1][1] * nums[i];
                        dp[i][0] = nums[i];
                    } else if (dp[i - 1][1] < 0) {
                        // 上一个最大值小于0
                        dp[i][1] = nums[i];
                        dp[i][0] = dp[i - 1][0] * nums[i];
                    } else {
                        if (dp[i - 1][1] == 0) {
                            dp[i][1] = nums[i];
                        } else {
                            dp[i][1] = dp[i - 1][1] * nums[i];
                        }
                        dp[i][0] = dp[i - 1][0] * nums[i];
                    }
                } else {
                    dp[i][0] = 0;
                    dp[i][1] = 0;
                }
            }

            int max = dp[0][1];
            for (int i = 1; i < dp.length; i++) {
                if (dp[i][1] > max) {
                    max = dp[i][1];
                }
            }
            return max;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        int[] nums = new int[]{3,0, -2,1};
        Solution solution = new P152MaximumProductSubarray().new Solution();
        System.out.println(solution.maxProduct(nums));
        // TO TEST
    }

}